home *** CD-ROM | disk | FTP | other *** search
/ Collection of Tools & Utilities / Collection of Tools and Utilities.iso / basic / ubas830.zip / MPQS#10.ASM < prev    next >
Assembly Source File  |  1989-04-04  |  18KB  |  1,181 lines
  1. ;MPQS#10.ASM
  2. ;    MACHINE LANGUAGE SUBROUTINE
  3. ;    FOR MULTIPLE POLYNOMIAL QUADRATIC SIEVE
  4. ;
  5. ;    Original Version           1987 by YUJI KIDA
  6. ;    Fantastic? English Version 1988 by Yuji KIDA
  7.  
  8.     INCLUDE    UB.MAC
  9.  
  10.     JMP    START0
  11.  
  12.     EVEN
  13. SIEVESEG    DW    ?
  14.  
  15. SEGSTEP    DW    ?
  16. SEGTOP    DW    ?
  17. SEGEND    DW    ?
  18.  
  19. MSIZE    DW    ?
  20. MWORDS    DW    ?
  21. ROWWORDS    DW    ?
  22. OFF2ND    DW    ?
  23. OFF3RD    DW    ?
  24.  
  25. ROWINDEXMIN    DW    ?
  26. ROWINDEXNOW    DW    ?
  27. ROWINDEXNOW2    DW    ?
  28. ROWINDEXLIM    DW    ?
  29. ROWINDEXMAX    DW    ?
  30. DS_INDEX    DW    ?
  31.  
  32. SEGNOW    DW    ?
  33. OFFNOW    DW    ?
  34. MASKNOW    DW    ?
  35. ANSNOW    DW    ?
  36.  
  37. OFF1    DW    ?
  38. SEG1    DW    ?
  39. OFF2    DW    ?
  40. SEG2    DW    ?
  41.  
  42. N_OFF    DW    ?
  43. N_SEG    DW    ?
  44. X_OFF    DW    ?
  45. X_SEG    DW    ?
  46. Y_OFF    DW    ?
  47. Y_SEG    DW    ?
  48. WW_OFF    DW    ?
  49. WW_SEG    DW    ?
  50. XA_SEG    DW    ?
  51. YA_SEG    DW    ?
  52.  
  53. YR_SEG    DW    ?
  54. YR_SIZE    DW    ?
  55. YR_KOSU    DW    ?
  56. MAXLOW    DW    ?
  57. MAXHIGH    DW    ?
  58.  
  59. P_OFF    DW    ?
  60. P_SEG    DW    ?
  61. P_NOW2    DW    ?
  62.  
  63. STOP_PTR    DW    ?
  64.  
  65. ADR_NOW    DW    ?
  66. REENT    DB    ?,?
  67.  
  68. LOG_INI    DW    ?
  69. LOG_MAX    DW    ?
  70.  
  71.  
  72.  
  73. ;** COMMAND BRANCH
  74.  
  75.  
  76. START0:
  77.     MOV_AX    AR0        ;get COMMAND frm ARRAY[0]
  78.     MOV    BX,OFFSET CMD_TBL
  79.     SHL    AX,1
  80.     ADD    BX,AX
  81.     JMP    CS:[BX]
  82.  
  83. CMD_TBL:
  84.     DW    INIT,SIEVE,SIEVE_ANS,TEST_DIV,LPV
  85.     DW    SET_ROW,GAUSS,SQUARE_ANS,GET_DIV,RE_INIT
  86.  
  87.  
  88. ;
  89. ;** reinitilization if one could not find a factor after 1st 
  90. ;   GAUSSian elimination
  91. ;
  92. ; COMMAND#=9
  93.  
  94. RE_INIT:
  95.     ;erase the column corresponding to discarded X
  96.  
  97.     MOV    SI,CS:[ROWINDEXNOW]
  98. REINI10:
  99.     CMP    SI,CS:[ROWINDEXMAX]
  100.     JB    REINI15
  101.  
  102.     MOV    AX,SS
  103.     MOV    DS,AX
  104.     MOV    ES,AX
  105.     RETF
  106.  
  107. REINI15:
  108.     MOV    ES,CS:[SI]    ;*keep ES,SI through main loop
  109.     MOV    DI,CS:[OFF3RD]
  110.     SUB    DI,2
  111.     MOV    CX,CS:[MWORDS]
  112.     INC    CX
  113.     XOR    AX,AX
  114.     STD
  115.     REP    SCASW
  116.     CLD
  117.     LEA    BX,[DI+2]
  118.     MOV    AX,ES:[BX]
  119.     MOV    DX,8000H
  120. REINI20:
  121.     TEST    DX,AX
  122.     JNZ    REINI30
  123.     SHR    DX,1
  124.     JMP    REINI20        
  125. REINI30:                
  126.     ;NOW DX is the highest bit of [BX]
  127.     ;erase this bit in the other rows
  128.  
  129.     MOV    DI,CS:[ROWINDEXMIN]
  130. REINI40:
  131.     CMP    DI,SI
  132.     JE    REINI60        ;do not erase the bit itself
  133.     CMP    DI,CS:[ROWINDEXMAX]
  134.     JAE    REINI70        ;last pass
  135.     MOV    DS,CS:[DI]
  136.     TEST    [BX],DX
  137.     JZ    REINI60        ;not match
  138.  
  139.     PUSH    SI
  140.     MOV    SI,CS:[OFF2ND]
  141.     MOV    CX,CS:[MWORDS]
  142.     INC    CX
  143. REINI50:
  144.     MOV    AX,ES:[SI]
  145.     XOR    [SI],AX
  146.     ADD    SI,2
  147.     LOOP    REINI50
  148.     POP    SI
  149.  
  150. REINI60:
  151.     ADD    DI,2
  152.     JMP    REINI40
  153.  
  154. REINI70:
  155.     ;set corresponding unit vector
  156.  
  157.     MOV    DI,CS:[OFF2ND]
  158.     MOV    CX,CS:[MWORDS]
  159.     INC    CX
  160.     XOR    AX,AX
  161.     REP    STOSW        ;SET 07s
  162.     MOV    ES:[BX],DX    ;SET 1
  163.  
  164.     ;set pointers to X(),Y()
  165.  
  166.     SUB    BX,CS:[OFF2ND]
  167.     SHL    BX,1
  168.     SHL    BX,1
  169.     SHL    BX,1
  170. REINI110:
  171.     INC    BX
  172.     SHR    DX,1
  173.     JNC    REINI110
  174.     DEC    BX
  175.     MOV_AX    LSIZE
  176.     MUL    BX
  177.     MOV    BX,CS:[OFF3RD]
  178.     MOV    ES:[BX],AX
  179.  
  180.     ADD    SI,2
  181.     JMP    REINI10
  182.  
  183. ;
  184. ;** get exponents of each prime in the factorization of X
  185. ;
  186. ; COMMAND#=8
  187. ; INPUT Y
  188. ; OUTPUT SV%()
  189.  
  190. GET_DIV:
  191.     PUSH    BP
  192.  
  193.     LDS    SI,DWORD PTR CS:[Y_OFF]
  194.     MOV    BX,SI        ;MEMO dividend
  195.     MOV    ES,CS:[P_SEG]
  196.     MOV    DI,AR0+10    ;start at 2
  197.     MOV    CS:[OFFNOW],0
  198.  
  199.     STD
  200.     MOV    CX,CS:[MSIZE]
  201.     DEC    CX        ;skip -1
  202. GDIVLP:
  203.     MOV    BP,ES:[DI]    ;divisor
  204.     ADD    CS:[OFFNOW],2
  205.     ADD    DI,10
  206.     PUSH    CX
  207. GDIV10:
  208.     MOV    SI,BX
  209.     MOV    AX,[SI]
  210.     MOV    CX,AX        ;WORDS
  211.     SHL    AX,1
  212.     ADD    SI,AX        ;highest word adr
  213.     XOR    DX,DX    
  214. GDIV20:
  215.     LODSW
  216.     DIV    BP
  217.     LOOP    GDIV20
  218.     OR    DX,DX
  219.     JZ    GDIV100        ;divide if divisible
  220.  
  221.     POP    CX
  222.     LOOP    GDIVLP
  223.  
  224.     POP    BP
  225.     CLD
  226.     RETF
  227.  
  228. GDIV100:
  229.     MOV    AX,DS
  230.     MOV    DS,CS:[SIEVESEG]
  231.     MOV    SI,CS:[OFFNOW]
  232.     INC    WORD PTR [SI]
  233.     MOV    DS,AX
  234.     MOV    SI,BX
  235.     MOV    AX,[SI]
  236.     MOV    CX,AX        ;WORDS
  237.     SHL    AX,1
  238.     ADD    SI,AX        ;highest word adr
  239.     XOR    DX,DX    
  240.     LODSW
  241.     DIV    BP
  242.     PUSH    AX        ;value of highest word
  243.     JMP    SHORT GDIV120
  244. GDIV110:
  245.     LODSW
  246.     DIV    BP
  247. GDIV120:
  248.     MOV    [SI+2],AX
  249.     LOOP    GDIV110
  250.     POP    AX        ;value of highest word
  251.     OR    AX,AX
  252.     JNZ    GDIV10
  253.     DEC    WORD PTR [SI]    ;dec len if highest word=0
  254.     JMP    GDIV10
  255.  
  256. ;
  257. ;** GAUSSian elimination
  258. ;
  259. ;COMMAND#=4
  260. ;
  261.  
  262. GO_GAUSSNEXT_C:
  263.     JMP    GAUSSNEXT_C
  264.  
  265.  
  266. GAUSS:
  267.     MOV    SI,CS:[ROWINDEXNOW]
  268.     MOV    CS:[ROWINDEXLIM],SI
  269.     MOV    ES,CS:[SI]
  270.     XOR    DI,DI
  271.     MOV    CX,CS:[MWORDS]
  272.     MOV    AX,0FFFFH
  273.     REP    STOSW        ;STOPPER
  274.  
  275.     MOV    SI,CS:[ROWINDEXMIN]
  276.     MOV    CS:[ROWINDEXNOW],SI
  277.     MOV    ES,CS:[SI]
  278.     MOV    BX,CS:[OFF2ND]    ;START OFFSET(right column first)
  279.     SUB    BX,2        ;
  280.     MOV    DX,8000H    ;BIT MASK
  281.  
  282. ;* search this column and exchange the row with 1st nonzero
  283.  
  284. GAUSS10:
  285.     MOV    SI,CS:[ROWINDEXNOW]
  286.     JMP    SHORT GAUSS25
  287. GAUSS20:
  288.     MOV    SI,CS:[DS_INDEX]
  289.     ADD    SI,2
  290. GAUSS25:
  291.     MOV    CS:[DS_INDEX],SI
  292.     MOV    DS,CS:[SI]
  293.     TEST    [BX],DX
  294.     JZ    GAUSS20
  295.  
  296.     CMP    SI,CS:[ROWINDEXLIM]
  297.     JAE    GO_GAUSSNEXT_C    ;go to next row for no NONZERO
  298.     CMP    SI,CS:[ROWINDEXNOW]
  299.     JE    GAUSS40        ;already NONZERO
  300.  
  301.     ;swap POINTERs
  302.  
  303.     MOV    SI,CS:[DS_INDEX]
  304.     MOV    DI,CS:[ROWINDEXNOW]
  305.     MOV    AX,CS:[SI]
  306.     XCHG    AX,CS:[DI]
  307.     MOV    CS:[SI],AX
  308.  
  309.     MOV    AX,DS
  310.     MOV    ES,AX
  311.  
  312. ;* eliminate this column
  313.  
  314. GAUSS40:
  315.     MOV    SI,CS:[DS_INDEX]
  316.     ADD    SI,2
  317.     MOV    CS:[DS_INDEX],SI
  318.     MOV    DS,CS:[SI]
  319.  
  320.     TEST    [BX],DX
  321.     JZ    GAUSS40        ;do not change this row
  322.  
  323.     CMP    SI,CS:[ROWINDEXLIM]
  324.     JAE    GAUSSNEXT_RC    ;go to next row&column
  325.  
  326.     MOV    CX,CS:[ROWWORDS]
  327.     DEC    CX
  328.     XOR    SI,SI
  329.     EVEN
  330. GAUSS60:
  331.     MOV    AX,ES:[SI]
  332.     XOR    [SI],AX
  333.     INC    SI
  334.     INC    SI
  335.     LOOP    GAUSS60
  336.  
  337.     JMP    GAUSS40
  338.  
  339.     ;next column or next row&column
  340.  
  341. GAUSSNEXT_RC:
  342.     MOV    SI,CS:[ROWINDEXNOW]
  343.     ADD    SI,2
  344.     MOV    CS:[ROWINDEXNOW],SI
  345.     MOV    ES,CS:[SI]
  346. GAUSSNEXT_C:
  347.     ROR    DX,1
  348.     JNC    GAUSS100
  349.     SUB    BX,2
  350.     JC    GAUSSEND
  351. GAUSS100:
  352.     JMP    GAUSS10
  353. GAUSSEND:
  354.     MOV    AX,CS:[ROWINDEXNOW]
  355.     MOV    CS:[ROWINDEXNOW2],AX
  356.     SUB    AX,CS:[ROWINDEXMIN]
  357.     SHR    AX,1
  358.     MOV    BX,AR3        ;return current rank in
  359.     MOV    CS:[BX],AX    ;ARRAY[3]
  360.  
  361.     MOV    AX,SS
  362.     MOV    DS,AX
  363.     MOV    ES,AX
  364.     RETF
  365.  
  366. ;
  367. ;** return a value got by SIEVE
  368. ;
  369. ;COMMAND#=5
  370. ;OUTPUT    X=OFFSET 
  371. ;     =-1 NO MORE DATA
  372.  
  373. SIEVE_ANS:
  374.     MOV    ES,CS:[SIEVESEG]
  375.     MOV    DI,CS:[ADR_NOW]
  376.     OR    DI,DI
  377.     JZ    GETD100
  378. GETD10:
  379.     MOV    AX,CS:[LOG_MAX]
  380.     MOV    CX,DI
  381.     NEG    CX
  382. GETDLP:
  383.     SCASB
  384.     JAE    GETIT
  385.     LOOP    GETDLP
  386. GETNO:
  387.     MOV    AX,8001H
  388.     MOV    DX,1
  389.     MOV    BX,DI
  390. GETOUT:
  391.     LES    DI,DWORD PTR CS:[X_OFF]
  392.     STOSW
  393.     MOV    ES:[DI],DX
  394.     MOV    CS:[ADR_NOW],BX
  395.     MOV    AX,SS
  396.     MOV    ES,AX
  397.     RETF
  398.  
  399. GETIT:
  400.     MOV    AX,1
  401.     MOV    DX,DI
  402.     DEC    DX
  403.     JNZ    GETIT20
  404.     XOR    AX,AX
  405. GETIT20:
  406.     MOV    BX,DI
  407.     JMP    GETOUT    
  408.  
  409.  
  410. GETD100:
  411.     TEST    CS:[REENT],-1
  412.     JNZ    GETNO
  413.     MOV    CS:[REENT],-1
  414.     JMP    GETD10
  415.  
  416.     
  417. ;** do the SIEVING
  418.  
  419. ;COMMAND#=1
  420.  
  421. SIEVE:
  422.     ;initialize sieve
  423.  
  424.     MOV    AX,CS:[SIEVESEG]
  425.     MOV    DS,AX
  426.     MOV    ES,AX
  427.  
  428.     XOR    DI,DI
  429.     MOV    CX,8000H
  430.     MOV    AX,CS:[LOG_INI]
  431.     REP    STOSW
  432.  
  433.     MOV    CS:[ADR_NOW],0
  434.     MOV    CS:[REENT],0
  435.  
  436.     MOV    AX,CS:[P_SEG]
  437.     MOV    ES,AX    
  438.     MOV    BX,AR0+20    ;skip -1,2
  439.  
  440.     ;SIEVE MAIN
  441.  
  442.     MOV    CX,CS:[MSIZE]
  443.     DEC    CX        ;skip -1
  444.     DEC    CX        ;skip 2
  445.  
  446. SIEVE_MAINLP:
  447.     MOV    DI,ES:[BX]    ;STEP
  448.     MOV    ax,ES:[BX+8]    ;LOG
  449.  
  450.     MOV    SI,ES:[BX+4]    ;START
  451. SIEVE20:
  452.     SUB    [SI],AL
  453.     ADD    SI,DI
  454.     jnc    SIEVE20
  455.     MOV    ES:[BX+4],SI    ;R1_OFF(for next entry)
  456.  
  457.     MOV    SI,ES:[BX+6]    ;R2_OFF START
  458. SIEVE40:
  459.     SUB    [SI],AL
  460.     ADD    SI,DI
  461.     jnc    SIEVE40
  462.     MOV    ES:[BX+6],SI    ;R2_OFF(for next entry)
  463.  
  464.     ADD    BX,10        ;update POINTER
  465.     LOOP    SIEVE_MAINLP
  466.  
  467.     MOV    AX,SS
  468.     MOV    DS,AX
  469.     MOV    ES,AX
  470.     RETF
  471.     
  472.  
  473. ;
  474. ;* use large 'primes' left after division
  475. ;    (CALLED LARGE PRIME VARIATION)
  476.  
  477. ;COMMAND#=3
  478. ;OUTPUT
  479. ;exists:  AR[0]=1,AR[1]=OLD INDEX
  480. ;insert:  AR[0]=0,AR[1]=NEW INDEX
  481. ;discard: AR[0]=0,AR[1]=-1
  482.  
  483. LPV:
  484.     ; GET W
  485.  
  486.     LDS    SI,DWORD PTR CS:[WW_OFF]
  487.     LODSW
  488.     MOV    CX,AX        ;LEN
  489.     XOR    DX,DX
  490.     LODSW
  491.     CMP    CX,2
  492.     JB    LARGE10
  493.     JA    LARGE200
  494.     MOV    DX,[SI]
  495. LARGE10:
  496.     ;SEARCH FOR DX:AX IN ZR
  497.     ; SO ONLY NUMBERS <=2 WORDS CAN BE TREATED
  498.  
  499.     CMP    DX,CS:[MAXHIGH]
  500.     JA    LARGE200
  501.     JB    LARGE15
  502.     CMP    AX,CS:[MAXLOW]
  503.     JA    LARGE200
  504. LARGE15:
  505.     MOV    SI,CS:[YR_SEG]
  506.     MOV    DS,SI
  507.     MOV    ES,SI    
  508.  
  509.     ;FIRST BINARY SEARCH
  510.  
  511.     MOV    BX,CS:[YR_KOSU]
  512.     SHL    BX,1
  513.     MOV    DI,OFFSET INDEX
  514. LARGE20:
  515.     SHR    BX,1
  516.     CMP    BX,1
  517.     JBE    LARGE100
  518.  
  519.     MOV    CX,BX
  520.     AND    CL,0FEH
  521.     ADD    DI,CX
  522.     MOV    SI,CS:[DI]
  523.     CMP    DX,[SI+2]
  524.     JB    LARGE40        ;D:A<MEM
  525.     JA    LARGE45        ;D:A>MEM
  526.     CMP    AX,[SI]
  527.     JA    LARGE45        ;D:A>MEM
  528.     JE    LARGE50        ;D:A=MEM
  529. LARGE40:
  530.     SUB    DI,CX
  531.     JMP    LARGE20
  532.  
  533. LARGE45:
  534.     ADD    DI,2
  535.     DEC    BX
  536.     JMP    LARGE20
  537.  
  538. LARGE50:
  539.     ;if 2 large primes are equal
  540.  
  541.     SHR    SI,1
  542.     SHR    SI,1        ;offset of the old 'prime'
  543.     MOV    BX,AR1
  544.     MOV    CS:[BX],SI    ;return it in AR[1]
  545.  
  546.     MOV    BX,AR0
  547.     MOV    WORD PTR CS:[BX],1    ;signal the match
  548.     MOV    AX,SS
  549.     MOV    DS,AX
  550.     MOV    ES,AX
  551.     RETF
  552.  
  553. LARGE200:
  554.     MOV    SI,8001H
  555.     MOV    BX,AR1        ;return -1 in AR[1]
  556.     MOV    CS:[BX],SI
  557.     JMP    LARGERET
  558.  
  559.  
  560.     ;NEXT CHECK CURRENT POSITION
  561.  
  562. LARGE100:
  563.     MOV    SI,CS:[DI]
  564.     CMP    DX,[SI+2]
  565.     JB    LARGE140    ;D:A<MEM
  566.     JA    LARGE110
  567.     CMP    AX,[SI]
  568.